package com.rising.bloom;

import java.util.BitSet;
import java.util.concurrent.atomic.AtomicInteger;

/**
 * @Author: rising
 * @Description:
 * @Date: create in 2020/9/12 12:03
 */
public class BloomFilter {

    //默认布隆过滤器样本数
    private static int DEFAULT_SIZE = 10 * 10000;
    //默认左移位数
    private static int DEFAULT_LEFT = 4;
    //默认右移位数
    private static int DEFAULT_RIGHT = 16;
    private static Double DEFAULT_FALSE_POSITIVE_RATE = 0.001;
    private int needHashs;
    //布隆过滤器已使用总数
    private AtomicInteger sum = new AtomicInteger(0);
    private RotatingHash[] rotatingHashes;
    private BitSet bitSet;

    /**
     * 默认样本数是10万，误报率是千分之一
     */
    public BloomFilter() {
        this(DEFAULT_LEFT, DEFAULT_RIGHT, DEFAULT_SIZE, DEFAULT_FALSE_POSITIVE_RATE);
    }

    /**
     *
     * @param size  样本数
     * @param falsePositiveRate  误报率
     */
    public BloomFilter(int size, Double falsePositiveRate) {
        this(DEFAULT_LEFT, DEFAULT_RIGHT, size, falsePositiveRate);
    }

    /**
     * 采用的是位移Hash，所以需要提供左位移数，右位移数
     * @param left
     * @param right
     * @param size   样本数
     * @param falsePositiveRate    误报率
     */
    public BloomFilter(int left, int right, int size, Double falsePositiveRate) {
        //计算布隆过滤器总空间，利用已经网上已经推导的公式
        int length = (int)Math.ceil(-Math.log(falsePositiveRate) / (Math.log(2) * Math.log(2))) * size;
        bitSet = new BitSet(length);
        //计算需要的hash函数总数
        needHashs = (int) Math.ceil(0.7 * length / size);
        rotatingHashes = new RotatingHash[needHashs];
        for (int i = 0; i < needHashs; i++) {
            rotatingHashes[i] = new RotatingHash(left + i, right + i, length - 1);
        }
    }

    /**
     * 添加方法
     * @param value
     */
    synchronized public void add(String value) {
        sum.incrementAndGet();
        //通过不同的hash计算出索引，将其所在的位置设置1
        for (RotatingHash rotatingHash : rotatingHashes) {
            bitSet.set(rotatingHash.rotatingHash(value), true);
        }
    }

    /**
     * 必须所有的hash计算值所在的位置都为1，才能返回true（存在误判率）
     * 布隆过滤器认为不存在的一定不存在
     * @param value
     * @return
     */
    public boolean contain(String value) {
        if (value == null) {
            return false;
        }
        boolean ret = true;
        for (RotatingHash rotatingHash : rotatingHashes) {
            ret = ret && bitSet.get(rotatingHash.rotatingHash(value));
        }
        return ret;
    }

    /**
     * 获取总数
     * @return
     */
    public int getSum() {
        return sum.intValue();
    }

    /**
     * 位运算计算hash
     */
    public static class RotatingHash {
        //左移位数
        private int left;
        //右移位数
        private int right;
        //任意质数
        private int prime;

        public RotatingHash(int left, int right, int prime) {
            this.left = left;
            this.right = right;
            this.prime = prime;
        }

        public int rotatingHash(String key) {
            int hash, i;
            for (hash = key.length(), i = 0; i < key.length(); ++i) {
                hash = (hash << left) ^ (hash >> right) ^ key.charAt(i);
            }
            return Math.abs(hash % prime);
        }
    }
}
